#pragma once

#include<vector>

template<class T>
struct KOfMod
{
	size_t operator()(const T& t)
	{
		return (size_t)t;
	}
};

template<>
struct KOfMod<string>
{
	size_t operator()(const string& s)
	{
		size_t sum = 0;
		for (auto e : s)
			sum = sum * 131 + e;
		
		return sum;
	}
};

namespace open_address
{
	enum STATE
	{
		EMPTY,
		EXIST,
		DELETE,
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		STATE _state = EMPTY;
	};

	template<class K, class V, class Mod = KOfMod<K>>
	class Hash
	{
	public:
		Hash(size_t n = 10)
		{
			_v.resize(n);
		}

		bool insert(const pair<K, V>& kv)
		{
			if (find(kv.first)) return false;

			if (_n * 10 / _v.size() >= 7)
			{
				Hash<K, V, Mod> tmphash(_v.size() * 2);
				for (size_t i = 0; i < _v.size(); i++)
				{
					tmphash.insert(_v[i]._kv);
				}
				_v.swap(tmphash._v);
			}

			Mod mod;
			size_t hashi = mod(kv.first) % _v.size();
			while (_v[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _v.size();
			}
			_v[hashi]._kv = kv;
			_v[hashi]._state = EXIST;
			++_n;
			return true;
		}

		HashData<K, V>* find(const K& k)
		{
			Mod mod;
			size_t hashi = mod(k) % _v.size();
			while (_v[hashi]._state != EMPTY)
			{
				if (_v[hashi]._state == EXIST && _v[hashi]._kv.first == k)
				{
					return &_v[hashi];
				}
				else
				{
					++hashi;
					hashi %= _v.size();
				}
			}

			return nullptr;
		}

		bool erase(const K& k)
		{
			HashData<K, V> ret = find(k);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<HashData<K, V>> _v;
		size_t _n = 0;
	};

	void test_hash1()
	{
		int a[] = { 10001,12,13,45,29,22 ,17 };
		Hash<int, int> hash;
		for (auto e : a)
		{
			hash.insert({ e,e });
		}
		hash.insert({ 19,19 });
	}

	void test_hash2()
	{
		string s[] = { "sort","left","right","child","parent" };
		Hash<string, int> hash;
		for (auto& e : s)
		{
			hash.insert({ e,1 });
		}
		hash.insert({ "adjustup",1 });
	}
}

namespace hash_table
{
	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next;

		HashNode(const pair<K, V>& kv)
			:_kv(kv),_next(nullptr)
		{}
	};

	template<class K,class V,class Mod = KOfMod<K>>
	class Hash
	{
		typedef HashNode<K, V> Node;
	public:
		Hash(size_t n = 10)
		{
			_v.resize(n, nullptr);
		}

		~Hash()
		{
			for (int i = 0; i < _v.size(); i++)
			{
				Node* cur = _v[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_v[i] = nullptr;
			}
		}

		bool insert(const pair<K, V>& kv)
		{
			if (find(kv.first)) 
				return false;

			Mod mod;

			if (_n == _v.size())
			{
				vector<Node*> newv(_n * 2, nullptr);
				for (int i = 0; i < _n; i++)
				{
					Node* cur = _v[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t hashi = mod(cur->_kv.first) % newv.size();
						cur->_next = newv[hashi];
						newv[hashi] = cur;
						
						cur = next;
					}
					_v[i] = nullptr;
				}
				_v.swap(newv);
			}

			size_t hashi = mod(kv.first) % _v.size();
			Node* newnode = new Node(kv);
			newnode->_next = _v[hashi];
			_v[hashi] = newnode;
			_n++;
			return true;
		}

		Node* find(const K& k)
		{
			Mod mod;
			size_t hashi = mod(k) % _v.size();
			Node* cur = _v[hashi];
			while (cur)
			{
				if (cur->_kv.first == k)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}

		bool erase(const K& k)
		{
			Mod mod;
			size_t hashi = mod(k) % _v.size();
			Node* prev = nullptr;
			Node* cur = _v[hashi];
			while (cur)
			{
				if (cur->_kv.first == k)
				{
					Node* next = cur->_next;
					if (prev == nullptr)
					{
						_v[hashi] = next;
					}
					else
					{
						prev->_next = next;
					}
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

	private:
		vector<Node*> _v;
		size_t _n = 0;
	};

	void test_hash_barket1()
	{
		int a[] = { 10001,12,13,45,29,22 ,17,22,23,24 };
		Hash<int, int> hash;
		for (auto e : a)
		{
			hash.insert({ e,e });
		}
		hash.insert({ 9,9 });
		hash.erase(9);
	}
}